package LeetCode.month02.day40;

import java.util.Arrays;
import java.util.PriorityQueue;

public class No1792 {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int n = classes.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->Double.compare((b[0]+1.0)/(b[1]+1.0)-(b[0]*1.0/b[1]),
                (a[0]+1.0)/(a[1]+1.0)-(a[0]*1.0/a[1])));
        queue.addAll(Arrays.asList(classes));

        while(extraStudents>0){
            int[] top = queue.poll();
            top[0]++;
            top[1]++;
            queue.add(top);
            extraStudents--;
        }

        double num = 0;
        while(!queue.isEmpty()){
            int[] top = queue.poll();
            num+=1.0*top[0]/top[1];
        }
        return num/n;
    }
}
